Synchronous Optical Networking (SONET) and Synchronous, Digital Hierarchy (SDH) are optical network standards. SONET and SDH use Time Division Multiplexing (TDM) to subdivide the bandwidth of an optical channel into smaller usable fragments called “time slots.” SONET and SDH provide a hierarchy of bandwidth granularities, specified as “STS-n,” that can be provisioned as end-to-end paths in an optical network. Higher bandwidth granularities are integer multiples of the lower bandwidth granularities (e.g., STS-1, STS-3c, STS-12c, STS-48c and so on for SONET).
SONET (see, ANSI standards document T1.105-2001, “Synchronous Optical Network (SONET)—Basic Description including Multiplex Structure, Rates, and Formats”, ITU-T Standards document, incorporated herein by reference) applies to optical networks in North America. SDH (see, G.707—“Network Node Interface for the Synchronous Digital Hierarchy (SDH),” incorporated herein by reference) applies to optical networks in Europe and the rest of the world.
Bandwidth fragmentation is a well-known network engineering issue in service provider transport networks. Communication links in the networks become fragmented as circuits are added and deleted over time, leaving behind “holes” in the transport pipe. Consequently, network efficiency is gradually lowered as the free bandwidth is evermore fragmented into smaller units: new, high-bandwidth circuits cannot be provisioned from the fragmented small units.
Fragmentation is a well-studied problem in computing systems going back over 30 years. In the very early computing systems (prior to the use of memory paging techniques), the main memory of a computer could become fragmented as programs got loaded into and erased from the main memory. The most common instance of fragmentation today is disk fragmentation, which causes large files to be “split” into multiple segments when contiguous free spaces on the disk are too small to hold entire files. In all cases, fragmentation impacts system efficiency, slowing system performance and leading to higher operating costs.
While the general problem of fragmentation has been addressed in various contexts, the problem of bandwidth fragmentation in optical transport networks is novel due to some unique constraints in the transport network. These constraints make prior art defragmentation solutions, such as disk defragmentation solutions, inappropriate.
The SONET and SDH standards stipulate that the bandwidth be provisioned as contiguous time slots on the link. (Due to their similarity from a defragmentation standpoint, only SONET will be referred to hereinafter, with the understanding that SDH is included.) For example, an STS-3c and an STS-12c circuit require three and 12 contiguous time slots of STS-1 level granularity respectively, STS-1 being the lowest cross-connect rate.
The provisioning of contiguous time slots is typically referred to as “contiguous concatenation.” As a consequence, fragmentation of a link can cause a new demand to be denied, even though sufficient number of slots exist, because they are noncontiguous.
This “lost” bandwidth can be recovered via a defragmentation operation that reengineers the circuits to new time slots in order to collate the free slots. A new standard called “virtual concatenation” (see, G.707, supra.) has been proposed in ITU-T to avoid the fragmentation problem by eliminating the contiguous slot requirement. However, until all edge network elements support the standard, fragmentation will remain a serious issue for SONET networks.
Link defragmentation has come to the fore with the advent of grooming cross-connect switches that enable an incoming signal passing through a node to be switched to any other time slot (Time Slot Interchange). While SONET networks have been traditionally engineered as rings, grooming switches have enabled mesh topologies consisting of these switches interconnected by wavelength division multiplexing (WDM) line systems. Since time slot interchange (TSI) meshes (or rings) enable a circuit to take any slot on each link along the path, each link can be defragmented independently to locally improve bandwidth efficiency.
The traditional approach in any defragmentation problem is a “push to the wall,” or PW, operation that moves all existing demands to one end of the container. Referring initially to prior art FIGS. 1A and 1B, shown are two such examples in the context of a SONET link. FIG. 1A shows the fragmented state of two links 110, 120 connecting a pair of nodes 130, 140. Thin lines, e.g., lines 150, 160 inside each link 110, 120, represent existing circuits. FIG. 1B shows the state of the links 110, 120 after a PW operation on each link 110, 120 independently. Such defragmentation is referred to as “intra-link defragmentation.”
Defragmentation may also occur across multiple links between the same pair of nodes (so-called “inter-link defragmentation”). Turning now to FIG. 1C, shown is the outcome of such an operation. Besides the normal motivation of creating contiguous free slots, inter-link defragmentation may also be performed to free a link 110, 120 so it can be disabled for maintenance.
The success of the defragmentation process is dependent on two metrics—the gain from defragmentation (the recovery of previously unprovisional time slots) and the “cost” of achieving the gain. In the SONET context, the cost of defragmentation is the number of circuits that move to new slots. Unlike the other instances of defragmentation such as memory and disk defragmentation, cost is a critical issue. This is because the service provider can defragment a live network and any circuit move increases the potential for traffic disruption.
Consequently, the goal of any defragmentation algorithm is not only to defragment a link optimally, but to also do it while attempting to minimize the number of circuit moves. Thus, while the PW operation suffices in other environments as a defragmentation mechanism, it is inappropriate here since it is not always the most cost effective. Accordingly, what is needed in the art is a way to defragment multiplexed communication links that takes into account the cost of defragmenting.